'''
跳表
'''

import random

class Node:
    def __init__(self, key, value, level):
        self.key = key
        self.value = value
        self.next = [None] * (level + 1)  # next[i] 表示在i层当前节点的next指针
    def __repr__(self):
        return f'{{key: {self.key}, value: {self.value}}}'


class SkipList:
    def __init__(self):
        self.head = Node(None, None, 0)
        self.max_level = 0
        self.size = 0

    def _random_level(self):
        level = 0
        while random.random() < 0.5:
            level += 1
        while self.max_level < level:
            self.head.next.append(None)
            self.max_level += 1
        return level

    def _most_right_in_level(self, cur, level, key):
        # 在level层 < key 的最右位置
        while cur.next[level] and cur.next[level].key < key:
            cur = cur.next[level]
        return cur

    def _most_right_in_Tree(self, key):
        # 在第0层(所有元素) < key 的最右位置
        cur = self.head
        for level in range(self.max_level, -1, -1):
            cur = self._most_right_in_level(cur, level, key)
        return cur

    def _get(self, key):
        less = self._most_right_in_Tree(key)
        find = less.next[0]
        return find if find and find.key == key else None

    def _add(self, key, value):
        find = self._get(key)
        if find:
            find.value = value
        else:
            level = self._random_level()
            node = Node(key, value, level)
            cur = self.head
            for lvl in range(self.max_level, level -1, -1):
                cur = self._most_right_in_level(cur, lvl, key)
            for lvl in range(level, -1, -1):
                cur = self._most_right_in_level(cur, lvl, key)
                node.next[lvl] = cur.next[lvl]
                cur.next[lvl] = node
            self.size += 1

    def _delete(self, key):
        find = self._get(key)
        if not find: return
        self.size -= 1
        cur = self.head
        for level in range(self.max_level, -1, -1):
            cur = self._most_right_in_level(cur, level, key)
            if cur.next[level] == find:
                cur.next[level] = find.next[level]



# ******************** 基本api ****************************
    def put(self, key, value):
        self._add(key, value)

    def get(self, key):
        target = self._get(key)
        if not target: raise KeyError(key)
        return target.value

    def remove(self, key):
        self._delete(key)

    def size(self):
        return self.size

    __getitem__ = get
    __setitem__ = put
    __delitem__ = remove
    __len__ = size

    def floor(self, key):
        less = self._most_right_in_Tree(key)
        next = less.next[0]
        return next.key if next and next.key == key else less.key

    def ceil(self, key):
        less = self._most_right_in_Tree(key)
        next = less.next[0]
        return next.key if next else None